package practice1_100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Offer04 {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        Queue<Integer> queue=new LinkedList<>();
        queue.poll();
        if(matrix.length==0||matrix[0].length==0)return false;
        int row=matrix.length-1,col=0;
        while(row>=0&&col<matrix[0].length){
            int flag=matrix[row][col];
            if(flag<target){//在列上面找
                for(int a=col;a<matrix[0].length;a++){
                    if(matrix[row][a]==target)return true;
                }
                col++;row--;
            }else if(flag>target){//在行上找
                for(int a=0;a<=row;a++){
                    if(matrix[a][col]==target) return true;
                }
                col++;row--;
            }else{
                return true;
            }
        }
        return false;

    }

    public static void main(String[] args) {
        boolean a= new Offer04().findNumberIn2DArray(new int[][]{{-1},{-1}},4);
        //,{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}
        System.out.println(a);
        //[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]

    }
}
